package com.leaf.spring.y201911.day14;

/**
 * 二分法查找
 * 
 * @author gaowenjin
 *
 */
public class BinarySearch {

	public static void main(String[] args) {

		BinarySearch binarySearch = new BinarySearch();

		int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };

		int target = 11;

		int b = binarySearch.binarySearch(arr, target);

		System.out.println("最终值 " + b);

	}

	public int binarySearch(int[] arr, int target) {

		int ret = -1;

		int left = 0;
		int right = arr.length - 1;

		while (left <= right) {

//			int middle = (left + right) / 2;
			int middle = (left + right) >> 1; //效率更高

			System.out.println("middle=" + middle + ";left=" + left + ";right=" + right);

			if (arr[middle] == target) {
				ret = middle;
				break;
			}

			// 如果目标值小于中间值，则目标值在middle的左侧
			if (arr[middle] > target) {
				right = middle - 1;
			} else

			// 如果目标值大于中间值，则目标值在middle的右侧
			if (arr[middle] < target) {
				left = middle + 1;
			}

		}

		return ret;

	}

}
